#include<bits/stdc++.h>
using namespace std;
const int N = 50002;

int n,m;
int h[N];
int maxn[N][32];
int minn[N][32];
int log2_[N];

int main(){
    scanf("%d%d",&n,&m);
    log2_[0] = 0;
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
        maxn[i][0] = minn[i][0] = h[i];
        log2_[i] = log2_[i-1] + ((2<<log2_[i-1])==i);
    }
    for(int len=1;len<=log2_[n];len++){
        for(int i=1;i<=n;i++){
            maxn[i][len] = max(maxn[i][len-1],maxn[min(n,i+(1<<(len-1)))][len-1]);
            minn[i][len] = min(minn[i][len-1],minn[min(n,i+(1<<(len-1)))][len-1]);
        }
    }
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        int x = r-l+1;
        int res = max(maxn[l][log2_[x]],maxn[r-(1<<log2_[x])+1][log2_[x]]) - 
                  min(minn[l][log2_[x]],minn[r-(1<<log2_[x])+1][log2_[x]]);
        printf("%d\n",res);
    }
    return 0;
}